package com.vint.lintcode;

import com.vint.common.TreeNode;

/**
 * 二叉查找树插入节点
 */
public class Lintcode85 {

	public TreeNode insertNode(TreeNode root, TreeNode node) {
		// write your code here
		if(null == root) {
			return node;
		}

		if (node.val == root.val) {
			return root;
		}
		if (node.val > root.val) {
			if (null == root.right) {
				root.right = node;
			} else {
				insertNode(root.right, node);
			}
		} else {
			if (null == root.left) {
				root.left = node;
			} else {
				insertNode(root.left, node);
			}

		}
		return root;
	}
}
